package com.chimm.main;

import java.util.Arrays;

/**
 * 希尔排序
 *      对于直接插入排序问题，数据量巨大时，可以使用希尔排序
 *
 * 1. 将数的个数设置为n，取奇数 k=n/2，将下标差值为k的数分为一组，构成有序序列
 * 2. 再取k=k/2，将下标差值为k的数分为一组，够成有序序列
 * 3. 重复第二步，直到k=1执行简单插入排序
 *
 *
 * 如何写成代码:
 *  1. 首先确定分的组数
 *  2，然后对组中元素进行插入排序
 *  3. 然后将length/2,重复1，2步，直到length=0为止
 */
public class SheelSort {

    public static void main(String[] args) {
        int[] a = {32, 43, 23, 13, 5}; //定义无序数组
        int d = a.length;

        while (d != 0) {
            d = d / 2;
            for (int x = 0; x < d; x++) { //分的组数
                for (int i = x + d; i < a.length; i += d) {//组中的元素，从第二个数开始
                    int j = i - d;//j为有序序列最后一位的位数
                    int temp = a[i];//要插入的元素
                    for (; j >= 0 && temp < a[j]; j -= d) {//从后往前遍历
                        a[j + d] = a[j];
                    }
                    a[j + d] = temp;

                }
                System.out.println(Arrays.toString(a));
            }
        }
    }
}
